package com.chengzhi.structure;

import java.util.HashMap;

/**
 *  LRU cache
 * @author: ruanchengzhi
 * @create: 2020-05-19 18:58
 **/
public class LRUCache<K, V> {

    private HashMap<K, Node> map;
    private int capacity;
    private Node head;
    private Node tail;
    private int size;

    LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.head = new Node(0, 0);
        this.tail = new Node(0, 0);

        head.prev = null;
        head.next = tail;
        tail.prev = head;
        tail.next = null;
    }

    V get(K key) {
        if (map.containsKey(key)) {
            Node<K, V> node = map.get(key);
            V value = node.val;
            removeNode(node);
            addToHead(node);
            return value;
        }
        return null;
    }

    void put(K key, V value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            removeNode(node);
            map.remove(key);
            size--;
        }
        Node node = new Node(key, value);
        map.put(key, node);
        if (size < capacity) {
            addToHead(node);
            size++;
        } else {
            map.remove(tail.prev.key);
            removeNode(tail.prev);
            addToHead(node);
        }
    }

    private void removeNode(Node<K, V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addToHead(Node<K, V> node) {
        node.next = head.next;
        node.next.prev = node;
        head.next = node;
        node.prev = head;
    }

    class Node<K, V> {
        K key;
        V val;
        Node prev;
        Node next;

        public Node(K key, V val) {
            this.key = key;
            this.val = val;
        }
    }
}
